//
// Created by liushuai on 2020/3/25.
//

#include "levelOrder.h"
vector<vector<int>> levelOrder(TreeNode *root) {
  queue<TreeNode *> current;
  vector<vector<int>> result;
  if (root) {
    current.push(root);
    while (!current.empty()) {
      int count = current.size();
      vector<int> layers;
      while (count) {
        TreeNode *node = current.front();
        current.pop();
        layers.push_back(node->val);
        if (node->left) current.push(node->left);
        if (node->right) current.push(node->right);
        count--;
      }
      if (layers.size() > 0) result.push_back(layers);
    }
  }
  return result;
}

void levelOrderRec(TreeNode *root, int layer,
                   std::vector<std::vector<int>> &result) {
  if (root) {
    // 不能直接push_back，通过判断result的大小获取层数否则层result的size可能会大于层数
    if (result.size() < layer + 1) result.push_back(std::vector<int>());
    result.at(layer).push_back(root->val);
    levelOrderRec(root->left, layer + 1, result);
    levelOrderRec(root->right, layer + 1, result);
  }
}
std::vector<std::vector<int>> levelOrderRec(TreeNode *root) {
  std::vector<std::vector<int>> result;
  levelOrderRec(root, 0, result);
  return result;
}
